import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;

public class 电话号码的字母组合 {
    
    public static void main(String[] args) {
        
        List<String> list = letterCombinations("23");
        list.stream().map(s -> s+" ").forEach(System.out::print);
        System.out.println("");

    }

    public static List<String> letterCombinations(String digits) {
        if (digits == null || digits.length() == 0)
            // 这里是特殊情况处理
            return new ArrayList<>();
        ArrayList<String> res = new ArrayList<>();
        StringBuilder sb = new StringBuilder();

        HashMap<String, String> hashMap = new HashMap<>();

        hashMap.put("2", "abc");
        hashMap.put("3", "def");
        hashMap.put("4", "ghi");
        hashMap.put("5", "jkl");
        hashMap.put("6", "mno");
        hashMap.put("7", "pqrs");
        hashMap.put("8", "tuv");
        hashMap.put("9", "wxyz");

        int len = digits.length();

        backtrackLetterCombinations(digits, res, sb, hashMap, 0, len);
        return res;
    }

    private static void backtrackLetterCombinations(String digits, List<String> res,
    StringBuilder sb, HashMap<String, String> hashMap,
    int letterIndex, int len) {
        
        if (letterIndex == len) {
            // 终止条件。注意，这里顺便收集了结果。因为本题需要在叶子收集结果
            // 有时，收集结果可能在下面的for循环中，这个取决于不同的题目
            res.add(sb.toString());
            return;
        }

        // 取当前的digit
        String digit = digits.substring(letterIndex, letterIndex+1);
        String letters = hashMap.get(digit);

        for (int i = 0; i < letters.length(); i++) {
            // 遍历每一种情况(选a,选b和选c)
            sb.append(letters.charAt(i));
            // 递归，这里的letterIndex加1表示下一层取字母的时候，要从下一个digit取了。
            backtrackLetterCombinations(digits, res, sb, hashMap, letterIndex+1, len);
            // 回溯
            sb.deleteCharAt(sb.length()-1);
        }
    }
}
